/**
 * TwoArrayMedian.java created by zhangzhidong 
 * at 上午11:15:42 2015年9月28日
 */
package newcoder.algorithm;

/**
 * 给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中所有数的上中位数。
 *例如：
 *arr1 = {1,2,3,4};
 *arr2 = {3,4,5,6};
 *一共8个数则上中位数是第4个数，所以返回3。
 *arr1 = {0,1,2};
 *arr2 = {3,4,5};
 *一共6个数则上中位数是第3个数，所以返回2。
 *要求：时间复杂度O(logN) 
 * @author Alex
 *
 */
public class TwoArrayMedian {

	/**
	 * 上午11:15:42 2015年9月28日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(algorithm(new int[]{1,2,3,4}, new int[]{3,4,5,6}));
		System.out.println(algorithm(new int[]{0,1,2}, new int[]{3,4,5}));
	}
	
	public static int algorithm(int arr1[],int arr2[]) {
		// TODO Auto-generated method stub

		return method(arr1, 0, arr1.length-1, arr2, 0, arr2.length-1);

	}
	public static int method(int arr1[],int begin1,int end1,int arr2[],int begin2,int end2){
		if(arr1==null || arr2==null) return -1;
		if(begin1==end1) return Math.min(arr1[begin1],arr2[begin2]);
		int offset = (end1-begin1+1) %2;
		int mid1 = (begin1+end1)/2;
		int mid2 =	(begin2+end2)/2;
		if(arr1[mid1]==arr2[mid2]) return arr1[mid1];
		else if(arr1[mid1]>arr2[mid2]){
			return method(arr1, begin1, mid1, arr2, mid2+offset, end2);
		}else{
			return method(arr1, mid1+offset, end1, arr2, begin2, mid2);
		}
		
	}
	

}
